package ans.p368;

import test.Entrance;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * #      368
 * 名称   最大整除子集
 * 链接   https://leetcode-cn.com/problems/largest-divisible-subset
 * 题解   [139](https://leetcode-cn.com/problems/largest-divisible-subset/solution)
 * 通过率 40.3%
 * 难道   中等
 */
//todo 回溯超时
public class Solution {
    @Entrance
    public List<Integer> largestDivisibleSubset(int[] nums) {
        List<Integer>[] ans = new List[1];
        Arrays.sort(nums);
        traceback(ans, new LinkedList<>(), nums, 0);
        return ans[0];

    }

    private void traceback(List<Integer>[] ans, List<Integer> list, int[] nums, int index) {
        if (index >= nums.length) {
            if (ans[0] == null) {
                ans[0] = new LinkedList<>(list);
            } else {
                if (ans[0].size() < list.size()) {
                    ans[0] = new LinkedList<>(list);
                }
            }
        }
        for (int i = index; i < nums.length; i++) {
            if (list.isEmpty() || nums[i] % list.get(list.size() - 1) == 0) {
                list.add(nums[i]);
                traceback(ans, list, nums, i + 1);
                list.remove(list.size() - 1);
            }else {
                traceback(ans, list, nums, i + 1);
            }
        }
    }
}